package Offer10;

import java.util.HashMap;
import java.util.Map;

/**
 * 青蛙跳台阶问题
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。
 * <p>
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 * @create 23737
 * @time 2021.1020
 */
public class Test_two {
    public static void main(String[] args) {
        System.out.println(new Solution_Two().numWays(3));
    }
}

class Solution_Two {
    //递归超时了
//    public int numWays(int n) {
//        int MODE = 1000000008;
//        if (n <= 1) return 1;
//        if (n == 2) return 2;
//        int num = 0;
//        if (n > 2) {
//            num += numWays(n - 1) + numWays(n - 2);
//        }
//        return num % MODE;
//    }

    //递归不超时，使用map来进行存储
    final int MODE = 1000000007;
//    public int numWays(int n) {
//        return numWays(n,new HashMap<>());
//    }
//    public int numWays(int n, Map<Integer,Integer> map){
//        if (n <= 1) return 1;
//        if (n == 2) return 2;
//        if (map.containsKey(n)){
//            return map.get(n);
//        }
//        int first = numWays(n-1,map)%MODE;
//        map.put(n-1,first);
//        int tail = numWays(n-2,map)%MODE;
//        map.put(n-2,tail);
//        int num = (first+tail)%MODE;
//        map.put(n,num);
//        return num;
//    }

    //使用循环
    public int numWays(int n) {
        if (n <= 1) return 1;
        if (n == 2) return 2;
        int pre = 1;
        int next = 2;
        for (int i = 2; i < n; i++) {
            int temp = next;
            next = (pre + next) % 1000000007;
            pre = temp;
        }
        return next;
    }
}
